package com.kiven.quicksort;

import java.util.*;


/**
 * 这里比较的数组中的数据不做限定(前提是能进行比较的数据)
 * 
 * 非递归方法实现快速排序的功能
 * 	   借助堆栈(stack)作为辅助工具，每经过1次划分，就把左边的子数组的左右指针(实际上是记录数组下标的两个整数)压入栈中，
 *   对右边的字数组继续划分，直到右边的子数组的左右指针满足：left >= right,弹栈，接着再重复上面的工作，划分、压栈...
 *   
 * 让该类实现Comparator接口，实现对map中不同类型的数据进行比较
 *   
 * @author liqingwen
 *
 */

public class NoRecursionQuickSortForGeneral2 implements Comparator {
	//在定义一个类边量时，尽量将该变量定义成接口类型，因为这样有利于它实现不同的实现类(多态的使用)
	private Map<Integer,Object> map;
	public NoRecursionQuickSortForGeneral2(Map<Integer,Object> map) {
		this.map = map;
	}
	
	public String toString() {
		StringBuffer sb = new StringBuffer();
		Set keyset = map.keySet();
		
		Iterator iter = keyset.iterator();
		while(iter.hasNext()) {
			sb.append(map.get(iter.next()));
			if(iter.hasNext()) {
				sb.append("**");
			}
		}
		return sb.toString();
	}
	
	@Override
	public int compare(Object o1,Object o2) {
			//获得两个数的哈希码，然后根据哈希码的大小来实现两个数的比较
			int hashcode1 = o1.hashCode();   
			int hashcode2 = o2.hashCode();
			
			if(hashcode1 > hashcode2) return 1;
			if(hashcode1 == hashcode2) return 0;
			return -1;
	}
	
	/**
	 * 使用Map来实现数组的比较，其中是用键值对的形式，因为在map中存放的不同的数据类型，然后用键值来模仿数组中的下标
	 * 
	 * @param mapSource 待排序数组的键值对
	 * @param left  模拟数组的左指针
	 * @param right 模拟数组的右指针
	 * @return 返回的是已经排完序的map
	 */
	public int position(Map<Integer,Object> mapSource,int left,int right) {
		Object obj,temp;
		int leftPtr = left-1;
		int rightPtr = right;
		
		//获得map中最大key所对应的值，也就是模拟数组中最大下标所对应的值
		obj = mapSource.get(right);
		
		while(true) {
			while(this.compare(mapSource.get(++leftPtr), obj) < 0);
			while((leftPtr < rightPtr) && (this.compare(mapSource.get(--rightPtr), obj) > 0));
			
			if(leftPtr >= rightPtr) break;
			else {
				temp = mapSource.get(leftPtr);
				mapSource.put(leftPtr, mapSource.get(rightPtr));
				mapSource.put(rightPtr, temp);
			}
			
		}
		
		temp = mapSource.get(leftPtr);
		mapSource.put(leftPtr, obj);
		mapSource.put(right, temp);
		
		return leftPtr;
	}
	
	/**
	 * 
	 * @param map	待排序数组
	 * @param left 	模拟完了的数组的左下标
	 * @param right  模拟完了的数组的右下标
	 */
	public void mapSort(Map<Integer,Object> map,int left,int right) {
		LinkedStack ls = new LinkedStack();
		Map<Integer,Object> m = map;
		int i = left;
		int j = right;
		int p = -1;
		
		
		while(true) {
			p = position(m, i, j);
			if(p-i>1) {
				ls.push(i, p-1);
			}
			
			i = p+1;
			
			if(i >= j) {
				if(!ls.isEmpty()) {
					Node node = ls.pop();
					i = node.getLeft();
					j = node.getRight();
				}
				else break; 
			}
		}
		
	}
	
	
	public static void main(String[] args) {
		Map<Integer,Object> map = new HashMap<Integer,Object>();
		map.put(0, 123);
		map.put(1, 121);
		map.put(2, 122);
		map.put(3, 1.2);
		map.put(4, "Kiven");
		map.put(5, 198);
		NoRecursionQuickSortForGeneral2 qs = new NoRecursionQuickSortForGeneral2(map);
		
		System.out.println("排序前的数组");
		System.out.println(qs.toString());
		
		//调用排序方法
		qs.mapSort(map, 0, map.size()-1);
		
		System.out.println("排序后的数组");
		System.out.println(qs.toString());
	}
}
